Оглавление 1. Математика 1.1. Теория чисел и геометрия 1.2. Дискретные структуры (DS) 1.3. Другие области математики 2. Компьютерные науки 2.1. Основы программирования (Programming Fundamentals) 2.2. Алгоритмы и сложность (Algorithms and Complexity) 2.3. Другие области Computer Science (все - исключены) 3. Разработка программного обеспечения - Software Engineering (SE) 1. Математика 1.1. Теория чисел и геометрия - целые числа, операции (включая возведение в степень), сравнение - свойства целых чисел (положительные, отрицательные, четные, нечетные, делимые, простые) - дроби, проценты - точка, вектор, декартовы координаты, двумерная целочисленная решетка - Евклидово расстояние, теорема Пифагора - отрезок прямой, свойства пересечения - угол - треугольник, прямоугольник, квадрат - многоугольник (вершина, сторона, простой, выпуклый, внутренность/внешность) ? окружность х вещественные числа, триогонометрические функции 1.2. Дискретные структуры (DS) DS1. Функции, отношения и множества - функции (surjections, injections, inverses, композиция) - отношения (рефлексивность, симметрия, транзитивность) отношение эквивалентности, отношения первого порядка отношения n-го порядка, лексикографический порядок - множества (диаграмма Виена, дополнения, декартово произведение мощность множества) - принцип Pigeonhole DS2. Базовая логика - Логика высказываний (Propositional logic) - Logical connectives (включая их основные свойства) - Таблицы истинности - Predicate logic (логика предикатов?) - Universal and existantial quantification - Modus ponens and modus tollens Исключено - нормальные формы DS3. Методы доказательств - Понятия : следствие (импликация), converse, inverse, contraposotive, отрицание, противоречие (contradiction) - Прямое доказательство, доказательства: контрпримером (by counterexample), от противного (by contraposition), by contradiction - Математическая индукция - Сильная индукция (complete induction) - Рекурсивные математические определения (включая взаимно рекурсивные определения) DS4. Основы счисления (Basics of counting) - Counting arguments (правила сумм и произведений, принципы включения/исключения, арифметическая и геометрическая прогрессии, числа Фибоначчи) - принцип Pigeonhole (для получения границ) - перестановки и сочетания (основные определения) - факториал, биноминальные коэффициенты DS5. Графы и деревья - Деревья (связные, без циклов, №вершин = №ребер + 1, упорядоченные(ordered)/не упорядоченные ) - Неориентированные графы (степень вершины (degree), путь, цикл, связность Эйлеров/Гамильтонов путь/цикл, лемма "handshaking") - Ориентированные графы (in-degree,out-degree, ориентированный путь/цикл, Эйлеров/Гамильтонов путь/цикл) - Остовные деревья - Стратегии обхода (определяющие порядок обхода вершин для упорядоченных деревьев) - "Декорированные" графы: с метками/весами/цветами вершин и ребер - Мультиграфы, графы с self-loops (дугами из себя в себя?) ? Планарные графы, двудольные графы, гиперграфы Исключено - дискретная вероятность 1.3. Другие области математики ? Многочлены, матрицы и операции с ними, Solid geometry Исключено: (линейная) алгебра, исчисления, теория вероятностей, статистика 2. Компьютерные науки 2.1. Основы программирования (Programming Fundamentals) PF1. Основные конструкции (для абстрактных машин) - основы синтаксиса и семантики высокоуровневого языка - переменные, типы, выражения, присваивания - простой ввод-вывод - условные и итерационные управляющие структуры - функции и передача параметров - структурная декомпозиция PF2. Алгоритмы и решение задач - стратегии решения задач - понять-запланировать-сделать-проверить - separation of concerns (разбиение на подзадачи ?) - обобщение, специализация, различение случаев, working backwards - роль алгоритмов в процессе решения задач - стратегии реализации алгоритмов - стратегии отладки - концепция (concept) и свойства алгоритмов (корректность, эффективность) PF3. Фундаментальные структуры данных - примитивные типы (логический, целый, символьный) - массивы (включая многомерные) - записи - строки и обработка строк - статическое и стековое размещение (элементы автоматического управления памятью) - связанные стуктуры (linked structures) линейные и ветвящиеся (списки и деревья) - стратегии реализации связанных структур в статической памяти - стратегии реализации стеков и очередей - стратегии реализации графов и деревьев - стратегии выбора правильных структур данных - абстрактные типы данных, очередь с приоритетами, динамическое множество (dynamic set), динамическая карта? (dynamic map) ? представление данных в памяти, heap allocation, runtime storage management, указатели и ссылки, стратегии реализации хеш-таблиц, длинная арифметика целых чисел Исключено: числа с плавающей точкой PF4. Рекурсия - концепция рекурсии - рекурсивные математические функции - простые рекурсивные процедуры (включая взаимную рекурсию) - стратегия "Разделяй и властвуй" (Divide-and-conquer) - рекурсивный backtracking (полный перебор) ? реализация рекурсии PF5. ? Программирование, управляемое событиями Однако - нужно уметь работать с библиотеками 2.2. Алгоритмы и сложность (Algorithms and Complexity) Цитата из [1 - CC 2001] "Алгоритмы лежат в основе компьютерных наук и разработки программного обеспечения". Реальная производительность любой программной системы зависит только от двух вещей: (1) выбранного алгоритма, (2) эффективности его реализации. Поэтому разработка хорошего алгоритма критична для производительности всех программных систем. Более того, изучение алгоритмов способствует решению проблем независимо от языка/парадигмы программирования, аппаратного обеспечения и других аспектов реализации. AL1. Основы анализа алгоритмов - спецификация алгоритма, предусловие, постусловие, корректность, инварианта - асимптотический анализ верхней границы сложности (неформально - худший случай) - понятие O - стандартные классы сложности (постоянная, логарифмическая, линейная, O(N*LogN), квадратичная, кубическая, экспоненциальная) - компромиссы/противоречия производительности и памяти AL2. Алгоритмические стратегии - стратегии проектирования простых циклов - полный перебор (Brute-force) - жадный алгоритм (Greedy) - разбиение на подзадачи (Devide-and-conquer) - backtracking (рекурсивный и нерекурсивный) - ветвей и границ - сопоставление образцов (pattern matching) и алгоритмы на строках/текстах - динамическое программирование Исключено : эвристики, алгоритмы приближенных вычислеинй AL3. Фундаментальные вычислительные алгоритмы - на целых числах алгоритм Евклида, проверка на простоту(O(sqrt(N))), решето Эратосфена, эффективное возведение в степень - простейшие итеративные алгоритмы min, max, гистограмма, bucket sort (сортировка черпаком?) - алгоритмы последовательного и двоичного поиска - поиск исключением, "slope" поиск - квадратичные алгоритмы сортировки (выборки, вставки) - разбиение, нахождение порядковых статистик с помощью разбиений, QuickSort - O(N*LogN) алгоритмы сортировки (HeapSort, сортировка слиянием) - деревья двоичного поиска - представления графов (список смежности, матрица смежности) - обходы упорядоченных деревьев - поиски в ширину и глубину на графах - алгоритмы кратчайших путей (Дейкстра и Флойд) - транзитивное замыкание (алгоритм Флойда) - минимальное остовное дерево (алгоритмы Крускала и Прима) - топологическая сортировка - построение связных компонент неориентированного графа - построение (существование?) Эйлерова пути/цикла ? хеш-таблицы Исключено: простые алгоритмы на вещественных числах, максимальный поток, макисмальное паросочетание AL4. Распределенные алгоритмы : Исключено AL5. Basic Computability ? конечные автоматы, контекстно-свободная грамматика, AL6. Классы сложности P и NP - исключено AL7. Теория автоматов - исключено ? регулярные выражения, машина Тьюринга AL8. Анализ продвинутых алгоритмов - минимаксные алгоритмы для оптимальных игровых стратегий исключено: амортизационный анализ, randomized алгоритмы, Alpha-Beta pruning AL9. Криптографические алгоритмы - исключено AL10. Геометрические алгоритмы - на 2D-решетках - отрезки прямых: свойства, пересечения - расположение точки относительно простого многоугольника - минимальная выпуклая оболочка AL11. Параллельные алгоритмы: исключено 2.3. Другие области Computer Science (все - исключены) AR - Architecture and Organization OS - Operation Systems NC - Net-Centric Computing PL - Programmin Languages HC - Human-Computer Interaction GV - Graphics and Visual Computing IS - Intelligent Systems IM - Information Management SP - Social and Professional Issue CN - Computational Science 3. Разработка программного обеспечения - Software Engineering (SE) Цитата из [1 - CC 2001] "SE - дисциплина, связанная с применением теории, знаний и практики для эффективного построения программных систем, удовлетворяющих требований пользователей". Для IOI требуются методы разработки маленьких программных проектов одним разработчиком в сжатые сроки. SE1. Software design - основные принципы и концепции проектирования - примеры проектирования - структурированное проектирование В частности олимпиадники должны уметь: преобразовать абстрактный алгоритм в конкретную эффективную программу на одном из разрешенных языков программирования возможно с использованием стандартных или специальных библиотек. Обеспечивать в своих программах - считывание данных из текстовых файлов - вывод данных в текстовые файлы в соответствии с описанным простым форматом SE2. Использование API - использование библиотеки, описанной в задаче SE3. Software tools and environments Олимпиадники должны уметь: набирать и редактировать тексты программ компилировать и исполнять программы отлаживать программы SE4. Software processes Олимпиадники должны понимать различные этапы в процессе разработки решений и выбирать соответствующие подходы SE5. Software requirements and specification Олимпиадники должны уметь: трансформировать точное описание на естественном языке в задачу в терминах вычислительной модели, с учетом требований эффективности SE6. Software validation (тестирование ПО) - создание плана тестирования, генерация тестов - тестирование "черного" и "белого" ящиков - хорошо структурированный код - инспеция исходного текста - встроенные тесты SE7. Software evalution (не требуется) SE8. Software project management Олимпиадники должны уметь: - планировать время по ходу олимпиады - сравнивать риски альтернативных подходов - вести несколько версий во время разработки SE9. Component-based computing - исключено SE10. Формальные методы Олимпиадник должен уметь обосновывать корректность и эффективность алгоритмов. SE11. Software reliability : исключено SE12. Specialized system development : исключено